/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/flip-game-ii
   @Language: C++
   @Datetime: 19-06-13 16:28
   */

class Solution {
	bool dfs(string &s, unordered_map<string,bool> &mem){
		if(mem.count(s)) return mem[s];
		for(int i=0; i+1<s.length(); ++i){
			if(s[i]=='+' && s[i+1]=='+'){
				s[i]=s[i+1]='-';
				bool second=dfs(s,mem);
				s[i]=s[i+1]='+';
				if(!second)	return mem[s]=true;
			}
		}
		return mem[s]=false;
	}
public:
	/**
	 * @param s: the given string
	 * @return: if the starting player can guarantee a win
	 */
	bool canWin(string &s) {
		// write your code here
		unordered_map<string,bool> mem;
		return dfs(s,mem);
	}
};
